Dynamic Programming 3

LCS & Optimal Binary Search Tree
Subsequence
Common Subsequence

LCS(Longest-Common-Subsequence Problem)
LCS 1. xm=yn이면, zk=xm=yn이고, Zk−1은 Xm−1,Yn−1의 LCS이다. 2. xm≠yn이면, zk≠xm는 Z가 Xm−1과Y의 LCS임을 의미한다. 3. xm≠yn이면, zk≠yn는 Z가 X과Yn−1의 LCS임을 의미한다. C[i, j]= 0 ; i=0 || j=0 c[i-1, j-1]+1 ; i, j>0 && xi==yj max(c[i, j-1], c[i-1, j]) ; i, j>0 && xi≠yj
#include <iostream>
#define LU 0
#define UP 1
#define LE 2
struct array{
int* arr;
int length;
array(int* _arr, int _length): arr(_arr), length(_length){}
int operator[](int ind){
return arr[ind];
}
};
template <typename T>
struct twoPoint{
T *p1, *p2;
twoPoint(T* _p1, T* _p2): p1(_p1), p2(_p2) {}
~twoPoint(){
delete p1;
delete p2;
}
};
struct Table{
int m, n;
int** table;
Table(int _m, int _n): m(_m), n(_n){
this->table=new int*[this->m];
for(int i=0; i<this->m; ++i){
this->table[i]=new int[this->n];
}
}
~Table(){
for(int i=0; i<this->m; ++i) delete[] this->table[i];
delete[] this->table;
}
int* operator[](int n){
return this->table[n];
}
};
twoPoint<Table> LCS(array X, array Y){
int m=X.length, n=Y.length;
Table* b=new Table(m, n);
Table* c=new Table(m+1, n+1);
for(int i=0; i<n+1; ++i){
(*c)[i][0]=0;
}
for(int j=0; j<m+1; ++j){
(*c)[0][j]=0;
}
for(int i=0; i<m; ++i){
for(int j=0; j<n; ++j){
if(X[i]==Y[j]){
(*c)[i+1][j+1]=(*c)[i][j]+1;
(*b)[i][j]=LU;
} else if((*c)[i][j+1]>=(*c)[i+1][j]){
(*c)[i+1][j+1]=(*c)[i][j+1];
(*b)[i][j]=UP;
} else{
(*c)[i+1][j+1]=(*c)[i+1][j];
(*b)[i][j]=LE;
}
}
}
return twoPoint<Table>(c, b);
}
void PrintLCS(Table* b, array X, int i, int j){
if(i==-1 || j==-1) return;
if((*b)[i][j]==LU){
PrintLCS(b, X, i-1, j-1);
std::cout<<X[i]<<' ';
} else if((*b)[i][j]==UP) PrintLCS(b, X, i-1, j);
else PrintLCS(b, X, i, j-1);
}
int main(void){
int x[]={1, 2, 3, 2, 4, 1, 2};
int y[]={2, 4, 3, 1, 2, 1};
int szx=sizeof(x)/sizeof(int), szy=sizeof(y)/sizeof(int);
array X(x, szx), Y(y, szy);
twoPoint<Table> res=LCS(X, Y);
PrintLCS(res.p2, X, szx-1, szy-1);
return 0;
}
Optimal Binary Search Tree
레드 블랙 트리와 같이 균형 잡힌 트리는 O(lgn)의 검색 시간을 보장할 수 있다.

사전을 만들 때와 같이 단어에 대한 빈도수가 다를 경우, 서로 다른 키에 대하여 최적화되어 있는 트리를 생성할 수 있다.
사전에 존재하지 않는 단어에 대해 가상 키(dummy key) d_i를 추가로 구현한다.

기대 검색 비용(expected Search Cost)가 최소인 이진 검색 트리를
최적 이진 검색 트리(Optiaml Binary Search Tree)라고 한다
Expected Search Cost E[searchcostinT]=1+Σni=1depthT(ki)pi+Σni=0depthT(di)qi
최적 이진 검색 트리에서는 최적의 상태가 전체 높이가 최소일 필요는 없다.

n개의 노드를 가지는 이진트리의 전체 경우의 수(트리의 수가) \Omega(4^n/n^{3/2})이다.
Expected Search Cost e[i,j]= qi−1 ; j=j-1 mini≤r≤j{e[i,r−1]+e[r+1,j]+w(i,j)} ; i≤j
#include <iostream>
#include <climits>
template <typename T>
struct twoPoint{
T *p1, *p2;
twoPoint(T* _p1, T* _p2): p1(_p1), p2(_p2) {}
~twoPoint(){
delete p1;
delete p2;
}
};
struct Table{
int m, n;
float** table;
Table(int _m, int _n): m(_m), n(_n){
this->table=new float*[this->m];
for(int i=0; i<this->m; ++i){
this->table[i]=new float[this->n];
}
}
~Table(){
for(int i=0; i<this->m; ++i) delete[] this->table[i];
delete[] this->table;
}
float* operator[](int n){
return this->table[n];
}
};
twoPoint<Table> OptimalBST(float* p, float* q, int n){
Table* e=new Table(n+1, n+1);
Table* w=new Table(n+1, n+1);
Table* root=new Table(n-1, n-1);
for(int i=0; i<n; ++i){
(*e)[i][i]=q[i];
(*w)[i][i]=q[i];
}
for(int l=0; l<n-1; ++l){
for(int i=0; i<n-l-1; ++i){
int j=l+i;
(*e)[i][j]=INT_MAX;
(*w)[i][j]=(*w)[i][j-1]+p[i]+q[j];
for(int r=i; r<=j; ++r){
float t=(*e)[i][r-1]+(*e)[r+1][j]+(*w)[i][j];
if(t<(*e)[i][j]){
(*e)[i][j]=t;
(*root)[i][j]=r;
}
}
}
}
return twoPoint<Table>(e, root);
}
int main(void){
float p[]={.15, .10, .05, .10, .20};
float q[]={.05, .10, .05, .05, .05, .10};
int n=sizeof(p)/sizeof(float);
twoPoint<Table> res=OptimalBST(p, q, n);
}